package com.study.data.structure.sequencelist;

import java.io.Serializable;
import java.util.Iterator;

/**
 * 线性表
 *
 * @author YangGuGu
 */
public class SequenceList<T> implements Iterable<T>, Serializable {

  /**
   * 默认容量大小
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * 元素数组
   */
  private T[] elements;

  /**
   * 当前线性表的长度
   */
  private int size;

  public SequenceList() {
    this(DEFAULT_CAPACITY);
  }

  public SequenceList(int capacity) {
    this.elements = (T[]) new Object[capacity];
  }

  /**
   * 清空线性表
   */
  public void clear() {
    this.size = 0;
  }

  /**
   * 线性表是否为空
   *
   * @return true表示空
   */
  public boolean isEmpty() {
    return this.size == 0;
  }

  /**
   * 线性表的大小
   *
   * @return 大小
   */
  public int size() {
    return this.size;
  }

  /**
   * 返回线性表中的第 i 个元素
   *
   * @param i
   *     下标
   * @return 第 i 个元素
   */
  public T get(int i) {
    if (i < 0 || i >= this.size) {
      throw new RuntimeException("当前元素不存在");
    }
    return elements[i];
  }

  /**
   * 在线性表的第 i 个元素之前插入一个值为 element 的数据元素。
   *
   * @param i
   *     第 i 个元素
   * @param element
   *     数据
   */
  public void insert(int i, T element) {
    if (i < 0 || i > this.size) {
      throw new RuntimeException("插入的位置不合法");
    }
    if (i == this.elements.length) {
      resize(this.elements.length * 2);
    }
    // 把i位置空出来，i位置及其后面的元素依次向后移动一位
    for (int index = size; index > i; index--) {
      elements[index] = elements[index - 1];
    }
    // 把t放到i位置处
    elements[i] = element;
    // 元素数量+1
    this.size++;
  }

  /**
   * 向线性表中添加一个元素 element
   *
   * @param element
   *     数据
   */
  public void insert(T element) {
    if (this.size == this.elements.length) {
      resize(this.elements.length * 2);
    }
    this.elements[this.size++] = element;
  }

  /**
   * 删除并返回线性表中第 i 个数据元素。
   *
   * @param i
   *     待删除元素的位置
   * @return 第 i 个元素
   */
  public T remove(int i) {
    if (i < 0 || i > this.size - 1) {
      throw new RuntimeException("当前要删除的元素不存在");
    }
    // 记录i位置处的元素
    T result = elements[i];
    // 把i位置后面的元素都向前移动一位
    for (int index = i; index < size - 1; index++) {
      elements[index] = elements[index + 1];
    }
    // 当前元素数量-1
    this.size--;

    // 当元素已经不足数组大小的1/4,则重置数组的大小
    if (this.size > 0 && this.size < this.elements.length / 4) {
      resize(this.elements.length / 2);
    }
    return result;
  }

  /**
   * 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回 -1
   *
   * @param element
   *     数据元素
   * @return 数据元素在线性表中的位置
   */
  public int indexOf(T element) {
    if (element == null) {
      throw new RuntimeException("查找的元素不合法");
    }
    for (int i = 0; i < size; i++) {
      if (elements[i].equals(element)) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 重置线性表大小
   *
   * @param newSize
   *     新的大小
   */
  private void resize(int newSize) {
    // 定义一个临时数组，指向原数组
    T[] temp = elements;
    // 创建新数组
    elements = (T[]) new Object[newSize];
    // 把原数组的数据拷贝到新数组即可
    if (this.size >= 0) {
      System.arraycopy(temp, 0, elements, 0, this.size);
    }
  }

  @Override
  public Iterator<T> iterator() {
    return new SIterator();
  }

  private class SIterator implements Iterator<T> {
    private int current;

    SIterator() {
      this.current = 0;
    }

    @Override
    public boolean hasNext() {
      return this.current < size();
    }

    @Override
    public T next() {
      return elements[current++];
    }
  }
}
